package org.czl.leetCode1;

public class L2458_H {
    //dfn序
    int[] dfn = new int[100001];
    int dfn_index = 0;
    int[] deep = new int[100001];//每一个节点到头结点的深度
    int[] size = new int[100001];
    int[] lMax = new int[100003];
    int[] rMax = new int[100003];

    public int[] treeQueries(TreeNode root, int[] queries) {
        dfs(root, 0);
        for (int i = 1; i <= dfn_index; i++) {
            lMax[i] = Math.max(deep[i], lMax[i - 1]);
        }
        for (int i = dfn_index; i > 0; i--) {
            rMax[i] = Math.max(deep[i], rMax[i + 1]);
        }
        int n = queries.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int ret = queries[i];
            int s = size[dfn[ret]];
            int l = lMax[dfn[ret] - 1];
            int r = rMax[s + dfn[ret]];
            ans[i] = Math.max(l, r);
        }
        return ans;
    }

    public void dfs(TreeNode x, int k) {
        int i = ++dfn_index;
        dfn[x.val] = i;
        deep[i] = k;
        size[i] = 1;
        if (x.left != null) {
            dfs(x.left, k + 1);
            size[i] += size[dfn[x.left.val]];
        }
        if (x.right != null) {
            dfs(x.right, k + 1);
            size[i] += size[dfn[x.right.val]];
        }


    }
}
